package com.cuz.daileetcode.bat100;

public class 抽牌获胜概率 {


    private static double process(int n, int a, int b, int cur) {
        if (cur >= a && cur < b) {
            return 1;
        }
        if (cur >= b) {
            return 0;
        }
        int res = 0;
        for (int i = 1; i <= n; i++) {
            res += process(n, a, b, cur + i);
        }
        return res / (double) n;
    }

    public static double solution1(int n, int a, int b) {
        return process(n, a, b, 0);
    }

    public static double solution2(int n, int a, int b) {
        double[] dp = new double[b];
        for (int i = a; i < b; i++) {
            dp[i] = 1;
        }
        for (int i = b - 1; i >= 0; i--) {
            int res = 0;
            for (int j = 1; j < n; j++) {
                res += outReturn0(dp, i + j);
            }
            dp[i] = res / (double) n;
        }
        return dp[0];
    }

    private static double outReturn0(double[] arr, int index) {
        if (index < 0 || index >= arr.length) {
            return 0;
        }
        return arr[index];
    }

    /**
     * a<= 当前分数 <b 赢
     * 当前分数>=b 输
     * 当前分数<a 继续抽牌
     * <p>
     * 1. 当前分数+抽到分数x 远小于 a
     * f（x）=f(x+1)+f(x+2)+...f(x+n-1)
     * f(x+1)=f(x+2)+f(x+3）+...+f(x+n-1)+f(x+n)
     * f(x)=f(x+1)+f(x+1）-f(x+n)
     * dp[x]=(2f(X+1)-f(x+n)/n
     * <p>
     * a=15 b=17  n=10
     * dp[1]=dp[2]+d[3]+dp[4]+dp[5]....dp[11]
     * dp[2]=dp[3]+dp[4]+dp[5]+.......+dp[11]+dp[12]
     * dp[1]=(2*dp[2]-dp[12])/n
     * {
     * ==============================
     * dp[x]=（2*dp[x+1]-dp[n+x+1])/n
     * ==============================
     * }
     * <p>
     * 2.当前分数+抽到分数x 可能大于a
     * a=15 b=17  n=10
     * dp[10]=dp[11]+dp[12]+dp[13]+dp[14]+dp[15]+dp[16]+0+0+0+0...+0;
     * 1       1              dp[20] 4个0
     * dp[11]=dp[12]+dp[13]+dp[14]+dp[15]+dp[16]+0+0+0+0
     * 1       1          dp[21] 4个0
     * <p>
     * dp[10]=2*dp[11]/n
     * {
     * =================
     * dp[x]=2*dp[x+1]/n
     * =================
     * }
     *
     * @param n 牌从1到n-1
     * @param a 下限
     * @param b 上限
     * @return 概率
     */
    public static double solution3(int n, int a, int b) {
        double[] dp = new double[b];
        for (int i = a; i < b; i++) {
            dp[i] = 1;
        }
        for (int i = b - 1; i >= 0; i--) {
            dp[i] = (2 * outReturn0(dp, i + 1))
                    / (double) n;
            if (i + 1 + n < a) {
                dp[i] -= outReturn0(dp, i + 1 + n)
                        / (double) n;
            }
        }
        return dp[0];
    }
}
